package edu.ustb.hash;

/**
 * @author ShiZhe
 * @create 2020-10-07 20:59
 * 哈希表的实现
 */
public class HashTable        //定义哈希表
{
    private DataItem[] hashArray;    // 数组形式
    private int arraySize;           //哈希表的大小
    private DataItem nonItem;        // 删除数据时,将被删除的数据设为nonItem
    //-------------------------------------------------------------
    public HashTable(int size)       //构造器，指定哈希表的大小
    {
        arraySize = size;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);   // 把nonItem的关键字设为-1
    }
    //-------------------------------------------------------------
    public void displayTable()       //显示哈希表
    {
        System.out.print("Table: ");
        for(int j=0; j<arraySize; j++)
        {
            if(hashArray[j] != null) {
                System.out.print(hashArray[j].getKey() + " ");
            } else {
                System.out.print("** ");  //该位置没有存数据
            }
        }
        System.out.println("");
    }
    //-------------------------------------------------------------
    public int hashFunc(int key)
    {
        return key % arraySize;       // 哈希函数
    }
    //-------------------------------------------------------------
    public void insert(DataItem item) // 插入数据
// 默认表未满，事实上哈希表是不允许存满的，哈希表的大小比实际存储的数据数要大。
    {
        int key = item.getKey();      // 获取数据项的关键字，用于计算哈希值
        int hashVal = hashFunc(key);  // 计算哈希值
        // 当前位置存有数据并且该数据未被删除
        while(hashArray[hashVal] != null &&
                hashArray[hashVal].getKey() != -1)
        {
            ++hashVal;                 // 查找下一个位置
            hashVal %= arraySize;      // 到达表的末尾时，hashVal值变成1,。构成循环，从而可以查找整个表
        }
        hashArray[hashVal] = item;    // 找到位置
    }  // end insert()
    //-------------------------------------------------------------
    public DataItem delete(int key)  // 根据关键字删除数据
    {
        int hashVal = hashFunc(key);  // 根据关键字计算哈希值

        while(hashArray[hashVal] != null)  // 该位置存有数据
        {                               // 两者的关键字是否相同
            if(hashArray[hashVal].getKey() == key)
            {
                DataItem temp = hashArray[hashVal]; // 保存删除的数据项，用于返回
                hashArray[hashVal] = nonItem;       // 删除
                return temp;                        // 返回删除的数据项
            }
            ++hashVal;                 // 关键字不相同，继续查找下一个
            hashVal %= arraySize;      //循环
        }
        return null;                  // 未找到
    }  // end delete()
    //-------------------------------------------------------------
    public DataItem find(int key)    // 表中是否存在该关键字的数据项
    {
        int hashVal = hashFunc(key);

        while(hashArray[hashVal] != null)
        {
            if(hashArray[hashVal].getKey() == key) {
                return hashArray[hashVal];
            }
            ++hashVal;
            hashVal %= arraySize;
        }
        return null;
    }
//-------------------------------------------------------------
}  // end class HashTable
